#pragma once
#include <string>
#include <iostream>

using namespace std;

class ordered_list
{
private:
	struct node
	{
		string data;
		node *next;

		node(string data = "", node *next = nullptr )
		{
			this->data = data;
			this->next = next;
		}		
	};

	node *head;
	node *tail;
	node *freehead;

	void insert(node *n)
	{
		if (head == nullptr)
		{
			head = tail = n;
			n->next = nullptr;
		}
		else
		{
			node *curr = head;
			node *prev = nullptr;
			while (curr->data.compare(n->data) < 0)
			{
				prev = curr;
				curr = curr->next;
				if (curr == nullptr)
					break;
			}
			//Add att begining
			if (prev == nullptr)
			{
				n->next = head;
				head = n;
			}
			//Add at end
			else if (curr == nullptr)
			{
				n->next = nullptr;
				tail = tail->next = n;
			}
			//Add in middle of list
			else
			{
				n->next = prev->next;
				prev->next = n;
			}			
		}
	}

public:

	ordered_list() : head(nullptr), tail(nullptr), freehead(nullptr) { }

	ordered_list(int size_free_list) : head(nullptr), tail(nullptr)
	{
		for (int i = 0; i < size_free_list; i++)
			freehead = new node("", freehead);
	}

	ordered_list(const ordered_list &that)
	{
		head = tail = freehead = nullptr;
		node *n = that.head;
		while (n != nullptr)
		{
			if (head == nullptr)
				head = tail = new node(n->data);
			else
				tail = tail->next = new node(n->data);
			n = n->next;
		}
		n = that.freehead;
		while (n != nullptr)
		{
			freehead = new node("", freehead);
			n = n->next;
		}
	}

	~ordered_list()	
	{ 
		while (head != nullptr)
		{
			node *d = head;
			head = head->next;
			delete d;
		}
		while (freehead != nullptr)
		{
			node *d = freehead;
			freehead = freehead->next;
			delete d;
		}
	}

	void add(string data)
	{
		if (freehead != nullptr)
		{
			node *n = freehead;
			n->data = data;
			freehead = freehead->next;
			insert(n);			
		}
		else
		{
			node *n = new node(data);
			insert(n);
		}
	}

	void print()
	{
		node *n = head;
		while (n != nullptr)
		{
			cout << n->data << ", ";
			n = n->next;
		}
		int i = 0;
		n = freehead;
		while (n != nullptr)
		{
			i++;
			n = n->next;
		}
		cout << endl << "Freelist size: " << i << endl;
	}

	void clear()
	{
		while (head != nullptr)
		{
			head->data = "";
			node *n = head;
			head = head->next;
			n->next = freehead;
			freehead = n;
		}
		tail = head;
	}

	class iterator
	{
	public:
		typedef iterator self_type;
		typedef node value_type;
		typedef node* pointer;
		typedef node& reference;
		typedef std::forward_iterator_tag iterator_category;
		typedef int difference_type;

		iterator(pointer ptr_) { this->ptr_ = ptr_; }

		self_type operator++()
		{
			self_type i = *this;
			ptr_ = ptr_->next;
			return i;
		}

		self_type operator++(int junk)
		{
			ptr_ = ptr_->next;
			return *this;
		}

		bool operator==(const self_type& rop) { return ptr_ == rop.ptr_; }
		bool operator!=(const self_type& rop) { return ptr_ != rop.ptr_; }

		reference operator*() { return *ptr_; }
		pointer operator->() { return ptr_; }

	private:
		pointer ptr_;
	};

	iterator begin() { return iterator(head); }
	iterator end() { return iterator(nullptr); }
};

